package TreeNodeSecond.SwordOffer;

public class InorderSuccessor {
    /**
     * 剑指 Offer II 053. 二叉搜索树中的中序后继
     * 给定一棵二叉搜索树和其中的一个节点 p ，找到该节点在树中的中序后继。如果节点没有中序后继，请返回 null 。
     * <p>
     * 节点 p 的后继是值比 p.val 大的节点中键值最小的节点，即按中序遍历的顺序节点 p 的下一个节点。
     * <p>
     * 示例 1：
     * <p>
     * 输入：root = [2,1,3], p = 1
     * 输出：2
     * 解释：这里 1 的中序后继是 2。请注意 p 和返回值都应是 TreeNode 类型。
     *
     * @param root
     * @param p
     * @return
     */
    public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
        TreeNode ans = null;
        TreeNode cur = root;
        while (cur != null) {
            if (cur.val <= p.val) {
                cur = cur.right;
            } else {
                ans = cur;
                cur = cur.left;
            }
        }
        return ans;
    }
}
